package CH01数组结构.LeetCode单调栈;

import java.util.ArrayDeque;
import java.util.Arrays;

public class LC503 {
    public int[] nextGreaterElements(int[] nums) {
        int length = nums.length;
        int[] ret = new int[length];
        Arrays.fill(ret, -1);
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < length * 2 - 1; i++) {
            while (!stack.isEmpty() && nums[i % length] > nums[stack.peek()]) {
                ret[stack.pop()] = nums[i % length];
            }
            stack.push(i % length);
        }
        return ret;
    }
}